CSE 444 Midterm

Autumn 2000

Name___________________________________

Total number of points: 100 (you can get a maximum of 100 out of the 110 points below)

1. [10 points] Design a relational schema for the E/R diagram below.

2. Consider a relation R(A,B,C,D,M,N,S) with functional dependencies
Aà M, Bà M, Cà N, Dà N, MNà S, CSà A, BSà D . Answer the following questions:

a. [5 points] Compute AB⁺

b. [5 points] Compute AC⁺

c. [5 points] Compute BC⁺

d. [10 points] Give an example of a database instance in which all given functional dependencies hold but ACà B does not hold:

A	B	C	D	M	N	S

3. Consider the following relational schema

                  WebPage(url, year, author)
                  Contains(pageUrl,dictWord)
                  Dictionary(word, origin)

where pageUrl is a foreign key in WebPage, and dictWord is a foreign key in Dictionary.

a. [10 points] Write a Relational Algebra expression tree that retrieves all urls of WebPages created in 1999 or later and containing some word of “Latin” origin.

b. For each of the questions below write SQL queries that answers that question:

i. [15 points] Retrieve the urls of all WebPages that contain only words of “Old English” origin.

ii. [20 points] An author’s vocabulary is the set of all words she used in all pages she created. Retrieve all authors with vocabularies of at least 10,000 distinct words.

iii. [20 points] Retrieve all pairs of urls whose corresponding web pages have at least 50 distinct words in common.

4. [10 points] Consider the following DTD The XML document below is not valid for this DTD. Add new elements and/or delete existing elements to make it valid for this DTD.

<email>j@partygoers.org </email>

</person>

</person>

<email>m@partygoers.org</email>

</person>

</party>

</party>

</person>

</party>

</memories>